/**
 * 字符串匹配
 *
 * 给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
 * 注意：不能使用任何内置的 BigInteger 库或直接将输入转换为整数。
 *
 * 示例 1:
 * 输入: num1 = "2", num2 = "3"
 * 输出: "6"
 *
 * 示例 2:
 * 输入: num1 = "123", num2 = "456"
 * 输出: "56088"
 *
 * 提示：
 *
 * 1 <= num1.length, num2.length <= 200
 * num1 和 num2 只能由数字组成。
 * num1 和 num2 都不包含任何前导零，除了数字0本身。
 */

/**
 * 我们观察两个数字相乘, 就是学的数学方法, 我们将两个乘数转化为数组可以发现,
 * 有三行数相加,这三行数可以看作是一个数字数组乘以另一个数字得到的, 我们在观
 * 察两个数的相加, 我们可以发现, 当两个数下标和相同时, 我们来将两个数相加,
 * 可以发现这两个数的下标加起来是一样的, 但是还是有点比较麻烦, 就是我们的下标
 * 对应是反过来的, 为了简化这个操作, 我们将两个原来的数组给反转一下就可以了
 * 时间复杂度 : O(n1 * n2)
 * 空间复杂度 : O(n1 + n2)
 */

public class Main {
    public String multiply(String num1, String num2) {

        // 要先转化为字符拼接函数在进行反转然后在进行转字符数组
        char[] ch1 = new StringBuffer(num1).reverse().toString().toCharArray();
        char[] ch2 = new StringBuffer(num2).reverse().toString().toCharArray();

        // 求出字符数组的长度
        int n1 = ch1.length;
        int n2 = ch2.length;

        // 我们将每个位数的和储存起来, 最后一次性进位
        // *** * *** 三位数 * 三位数的长度肯定是小于
        // 等于六位数的, 要是是六位数的, 最后一位肯定是进位了的
        int[] nums = new int[n1 + n2 - 1];

        // 这里我们求出每一个位置的数字让他们加起来
        for (int i = 0; i < n1; i++) {
            for (int j = 0; j < n2; j++) {

                // 这里将下标和相等的加入同一个位置
                int k = i + j;

                // 这里不要忘了 - '0'
                nums[k] += (ch1[i] - '0') * (ch2[j] - '0');
            }
        }

        // 将对应的位置添加入字符串拼接函数, 并进行进位
        StringBuffer ret = new StringBuffer();

        // 记录进位, 开始的进位为 0
        int tmp = 0;

        // 这里我们处理每一位和进位, 记住这个是反的结果, 所以后面还要反转一下结果
        for (int i = 0; i < n1 + n2 - 1; i++) {

            // 先加上进位
            nums[i] += tmp;

            // 这里取得进位数
            tmp = nums[i] / 10;

            // 这里是取进位的结构
            nums[i] %= 10;

            // 将结果加入字符串拼接函数
            ret.append(nums[i]);
        }

        // 这里要额外判断一下进位是否为零, 要是不为零要向前进位
        if (tmp != 0) {
            ret.append(tmp);
        }

        // 这里我们带到的数字后面可能为零, 反转过来就是前面为零, 只是不符合常规的,
        // 所以我们要排除这些零
        while (ret.length() > 1 && ret.charAt(ret.length() - 1) == '0') {
            ret.deleteCharAt(ret.length() - 1);
        }

        // 这里反转, 并转化为字符串
        return ret.reverse().toString();
    }
}